package com.ting.test.algorithms.递归和动态规划.从左往右的模型;


/**
 * 规定1对应A 2对应B 3对应C依此类推26对应Z那么一个数字字符串比如111就可以转化为AAA KA Ak
 * 给定一个只有数字字符组成的字符串str返回有多少种转化结果
 */
public class 字符串转化 {
    public static void main(String[] args) {
        String str = "2342234";
        int count = transfer(str.toCharArray());
    }

    private static int transfer(char[] arr) {
        if (null == arr) {
            return 0;
        }
        return process(arr, 0);
    }

    /**
     * process方法的含义是  字符串str从index位置开始转化，能够转化的结果数
     */
    private static int process(char[] arr, int index) {
        if (index == arr.length) {
            //base case
            return 1;//表示当前这种方法是可以行的
        }

        if (index > arr.length) {
            //base case
            return 0;//表示当前这种方法是不可以行的
        }
        if (arr[index] == '0') {
            //0是不能单独出现的，因此 这是有问题的
            return 0;
        }

        //考虑第一种情况，本次只转化当前位置的元素，那么由于字符串都是数字，范围在0~9，肯定是符合要求的
        int p1 = process(arr, index + 1);
        int p2 = 0;
        //考虑第二种情况， 转化当前位置和下一个位置，即两个元素转化一个字母
        int value = Integer.parseInt(String.valueOf(arr[index])) * 10 + Integer.parseInt(String.valueOf(arr[index + 1]));
        if (value <= 26) {
            p2 = process(arr, index + 2);
        }
        return p1 + p2;
    }


    /**
     * process方法的含义是  字符串为str从index位置开始转化，能够转化的结果数
     */
    private static int dp(char[] arr, int index) {
        int[] dp = new int[arr.length + 1];
        dp[arr.length] = 1;

        for (int i = arr.length - 1; i >= 0; i--) {
            //考虑第一种情况，本次只转化当前位置的元素，那么由于字符串都是数字，范围在0~9，肯定是符合要求的
            if(arr[i]=='0'){
                continue;
            }
            int p1 = dp[index+1];
            int p2 = 0;
            if (index + 1 < arr.length) {
                //考虑第二种情况， 转化当前位置和下一个位置，即两个元素转化一个字母
                int value = Integer.parseInt(String.valueOf(arr[index])) * 10 + Integer.parseInt(String.valueOf(arr[index + 1]));
                if (value <= 26) {
                    p2 = dp[index + 2];
                }
            }
            dp[i] = p1 + p2;
        }

        return dp[0];
    }
}
